package leetcode_acm.backtrack;

import java.util.LinkedList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月22日 19:35
 */
public class Combine {

    private List<List<Integer>> list;

    public List<List<Integer>> combine(int n, int k) {
        list = new LinkedList<>();
        backtrack(1,k,n,0,new LinkedList<>());
        return list;
    }
    private void backtrack(int startIndex,int k,int n,int pathSize,LinkedList<Integer> path){
        if(pathSize == k){
            list.add(new LinkedList<>(path));
            return;
        }
        //目前搜索区间中的元素是[i,n],个数是n - i + 1
        //目前还需要的元素个数是k - pathSize
        //于是当还存在可行解的方案是:n - i +1 >= k - pathSize
        //也就是i <= n +1 -k + pathSize
        int maxCombine = n +1 -k + pathSize;
        for(int i = startIndex;i <= maxCombine;i++){
            //做出选择
            path.addLast(i);
            //递归回溯
            backtrack(i+1,k,n,pathSize+1,path);
            path.removeLast();
        }
    }
}
